package net.xuele.learn.dancing.lru;

/**
 * @Author: yubo
 * @date: 11:00 2021/1/4
 * @Description: 类描述
 */

public class DoubleList {
    /**
     * 头尾虚节点
     */
    private Node head, tail;
    /**
     * 链表元素数
     */
    private int size;

    public DoubleList() {
        /**
         * 初始化双向链表的数据
         */
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
        size = 0;
    }

    /**
     * 在链表尾部添加节点 x，时间 O(1)
     *
     * @param x
     */
    public void addLast(Node x) {
        Node prev = tail.prev;
        prev.next = x;
        tail.prev = x;
        x.prev = prev;
        x.next = tail;
        size++;
    }

    /**
     * 删除链表中的 x 节点（x 一定存在）
     * <p>
     * 由于是双链表且给的是目标 Node 节点，时间 O(1)
     *
     * @param x
     */
    public void remove(Node x) {
        Node prev = x.prev;
        Node next = x.next;
        prev.next = next;
        next.prev = prev;
        size--;
    }

    /**
     * 删除链表中第一个节点，并返回该节点，时间 O(1)
     *
     * @return
     */
    public Node removeFirst() {
        if (head.next == tail)
            return null;
        Node next = head.next;
        remove(next);
        return next;
    }

    /**
     * 返回链表长度，时间 O(1)
     * @return
     */
    public int size() { return size; }
}
